package Leetcode100Hot;

/*
不同的二叉搜索树
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：
输入：n = 3
输出：5
示例 2：
输入：n = 1
输出：1

提示：

1 <= n <= 19
 */
public class _83不同的二叉搜索树 {


    //官解：方法一：DP
    //G(n): 长度为 n 的序列能构成的不同二叉搜索树的个数。
    //F(i,n): 以 i 为根、序列长度为 n 的不同二叉搜索树个数 (1≤i≤n)。
    //G(n) = ∑F(i,n)  {i = 1 ~ n}             (1)
    //F(i,n) = G(i−1)*G(n−i)                   (2)
    //==> G(n) = ∑G(i−1)⋅G(n−i)  {i = 1 ~ n}     (3)
    /*
    O(n^2) O(n)
    作者：力扣官方题解
    链接：https://leetcode.cn/problems/unique-binary-search-trees/solutions/329807/bu-tong-de-er-cha-sou-suo-shu-by-leetcode-solution/
     */
    class Solution {
        public int numTrees(int n) {
            int[] G = new int[n + 1];
            G[0] = 1;
            G[1] = 1;

            for (int i = 2; i <= n; ++i) {
                for (int j = 1; j <= i; ++j) {
                    G[i] += G[j - 1] * G[i - j];
                }
            }
            return G[n];
        }
    }


    //官解：方法二： 数学
    //O(n) O(1)
    /*
    作者：力扣官方题解
    链接：https://leetcode.cn/problems/unique-binary-search-trees/solutions/329807/bu-tong-de-er-cha-sou-suo-shu-by-leetcode-solution/
     */
    class Solution2 {
        public int numTrees(int n) {
            // 提示：我们在这里需要用 long 类型防止计算过程中的溢出
            long C = 1;
            for (int i = 0; i < n; ++i) {
                C = C * 2 * (2 * i + 1) / (i + 2);
            }
            return (int) C;
        }
    }

}
